package www.study.com;

//寻找两个正序数组的中位数 https://leetcode.cn/problems/median-of-two-sorted-arrays/
public class code4 {
    public static void main(String[] args) {

    }
    class Solution {
        //方法三：利用二分思想
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int rem1 = getKth(nums1,0,nums1.length - 1,nums2,0,nums2.length - 1,(nums1.length + nums2.length + 1) / 2);
            int rem2 = getKth(nums1,0,nums1.length - 1,nums2,0,nums2.length - 1,(nums1.length + nums2.length + 2) / 2);
            return (rem1 + rem1) / 2.0;
        }
        public int getKth(int[] num1,int start1,int end1,int[] num2,int start2,int end2,int k){
            int size1 = end1 - start1 + 1;
            int size2 = end2 - start2 + 1;
            if (size1 > size2) return getKth(num2,start2,end2,num1,start1,end1,k);
            if (size1 == 0) return num2[start2 + k - 1];
            if (k == 1) return Math.min(num1[start1],num2[start2]);
            int pos1 = start1 + Math.min(size1, k /  2) - 1;
            int pos2 = start2 + Math.min(size2, k / 2) - 1;
            if (num1[pos1] < num2[pos2]){
                return getKth(num1,pos1 + 1,end1,num2,start2,end2,k - (pos1 - start1 + 1));
            }else{
                return getKth(num1,start1,end1,num2,pos2 + 1,end2,k - (pos2 - start2 + 1));
            }
        }
        //方法二：利用归并排序的思想，时间复杂度0(n+m)
        /*public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int point1 = 0;//指向nums1的指针
            int point2 = 0;//指向nums2的指针
            int rem1 = 0;
            int rem2 = 0;
            int n = nums1.length;
            int m = nums2.length;
            boolean flag = (m + n) % 2 == 0;
            for (int i = 0; i <= (m + n) / 2; i++) {
                rem2 = rem1;
                if (point1 < n && (point2 >= m || nums1[point1] < nums2[point2])){
                    rem1 = nums1[point1++];
                }else{
                    rem1 = nums2[point2++];
                }
            }
            if (flag){
                return (rem1 + rem2) / 2.0;
            }else{
                return rem1 * 1.0;
            }
        }*/
        //方法一：暴力，时间复杂度0（(n+m)log(n+m)）
        /*public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int[] num = new int[nums1.length + nums2.length];
            for (int i = 0; i < nums1.length; i++) {
                num[i] = nums1[i];
            }
            for (int i = 0; i < nums2.length; i++) {
                num[i + nums1.length] = nums2[i];
            }
            Arrays.sort(num);
            double res = num[(num.length - 1) / 2] * 1.0;
            if ((num.length & 1) == 1){
                res = (res + num[(num.length - 1) / 2 + 1]);
            }
            return res;
        }*/
    }
}
